Ngày 3 tháng 4 năm 1965, ông tham gia vào trận đánh đầu tiên của Không quân Nhân dân Việt Nam, tấn công các máy bay của Hải quân Mỹ đang tập kích vào khu vực cầu Hàm Rồng – một cây cầu huyết mạch, yết hầu trên tuyến chi viện Bắc Nam.

Theo kế hoạch dự kiến của các chỉ huy Không quân Việt Nam, các máy bay Mỹ sẽ xuất phát từ hàng không mẫu hạm, qua điểm kiểm tra Hòn Mê để tập kích vào khu vực Hàm Rồng. Do đó, một biên đội do Đại úy Trần Hanh chỉ huy gồm Số 1 (mã hiệu 01) – Trần Hanh và số 2 (mã hiệu 03)– Phạm Giấy, sẽ làm nhiệm vụ nghi binh, xuất phát từ Nội Bài, bay dọc đường số 1, tiến về Nho Quan, sau đó sẽ bay chờ ở Cẩm Thủy để dẫn dụ tiêm kích đối phương rời xa khu vực chiến đấu. Sau đó, biên đội công kích do Phạm Ngọc Lan chỉ huy gồm số 1 (mã hiệu 05) – Phạm Ngọc Lan, số 2 (mã hiệu 06) – Phạm Văn Túc, số 3 (mã hiệu 07) – Hồ Văn Quỳ, số 4 (mã hiệu 08) – Trần Minh Phương, sẽ bay thấp dọc ven núi để tránh rada đối phương, theo hướng Tam Điệp, tiến vào khu vực chiến đấu từ hướng Hà Trung, lợi dụng thời cơ để tấn công. Trung tá Hoàng Ngọc Diêu được giao nhiệm vụ chỉ huy toàn bộ trận đánh.

Vào lúc 7 giờ, các đài rađa cảnh giới Việt Nam phát hiện một tốp máy bay Mỹ bay vào trinh sát khí tượng và mục tiêu. Lúc 9 giờ 40 phút, 60 lần máy bay cường kích các loại của Hải quân Mỹ cùng lúc bay vào đánh phá cầu Tào, cầu Đò Lèn và cầu Hàm Rồng. Lúc 9 giờ 47, biên đội nghi binh và yểm hộ cất cánh. Một phút sau biên đội tiến công cũng cất cánh theo kế hoạch đã dự kiến.

Lúc 10 giờ 09 phút, biên đội tiến công phân làm hai tốp, tiến vào khu vực tấn công, lợi dụng thế bất ngờ chiến thuật, khuấy đảo buộc các máy bay cường kích A-4 phải bỏ mục tiêu, đồng thời tiến hành không chiến với các máy bay tiêm kích F-8E hộ tống. Ban đầu, số 2 Phạm Văn Túc khai hỏa nhưng không trúng mục tiêu do tính sai khoảng cách. Phạm Ngọc Lan lệnh cho số 2 bình tĩnh, giữ đúng vị trí yểm hộ rồi cho máy bay vào tới cự ly bắn có hiệu quả và bắn trúng đối phương. Chiếc F-8E bị hạ thuộc biên chế Phi đoàn VF-211 Hải quân Hoa Kỳ, do Thiếu tá Spence Thomas điều khiển đã bị trúng đạn và hỏng nặng.[3] Chiếc máy bay này sau đó vẫn cố bay về và hạ cánh tại sân bay Đà Nẵng nhưng đã bị hư hỏng hoàn toàn và được tính là bị bắn rơi. Với chiến công này, Phạm Ngọc Lan trở thành phi công Việt Nam đầu tiên bắn rơi máy bay Mỹ trong không chiến.

Đội hình máy bay Hải quân Mỹ sau phút bất ngờ cũng tìm cách chống trả. Tuy nhiên, lúc 10 giờ 17 phút, số 2 Phạm Văn Túc bắn hạ tiếp một F-8E[4]. Bên cạnh đó, các khẩu đội phòng không của Việt Nam cũng bắn rơi và bị thương nhiều máy bay Mỹ, yểm hộ cho cả hai biên đội máy bay của Việt Nam thoát về an toàn.[5]